#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include <string>
#include <iostream>
#include "cstring"

using namespace  std;
#define MAX_VISIRNUM 100
void ShowVisit(int a[],int num)
{
    printf("访问序列:");
    for(int i=0;i<num;i++)
    {
        printf("%2d",a[i]);
    }
    printf("\n");
}
void ShowRam(int a[],int num)
{
    printf("内存块:");
    for(int i=0;i<num;i++)
    {
        printf("%3d",a[i]);
    }
    printf("\n");
}
void ShowFinal(int replaceNum,int lackingNum,int VisitNum)
{
    printf("\n缺页次数：%3d\n",lackingNum);
    printf("置换次数：%3d\n",replaceNum);
    printf("缺页率：%.2f%%\n",lackingNum*1.0/VisitNum*100);
    printf("命中率: %.2f%%\n",(1-lackingNum*1.0/VisitNum)*100);
}

void Init(int a[],int num)
{for(int i=0;i<num;i++){a[i]=-1; }}

int searchfuture(int fork[] ,int now,int VisitNum,int nowmessage)
{
    int i =now+1;
    for(i;i<VisitNum;i++)
    {
        if(fork[i]==nowmessage)
        {
            return i;
        }
    }
    return 1000;
}
void FIFO(int fork[], int PageNum, int PhyNum, int VisitNum)
{
    printf("********************************************************************************\n");
    printf("*                                                                              *\n");
    printf("*                                 FIFO算法                                     *\n");
    printf("*                                                                              *\n");
    printf("********************************************************************************\n");
    int ram[PhyNum]; Init(ram,PhyNum);
    int point=0;
    int judge=-1;
    int replaceNum = 0;//置换次数
    int lackingNum = 0;//缺页次数 
    for(int i =0;i<VisitNum;i++)
    {
        for(int j=0;j<PhyNum;j++)
        {
            if(ram[j]==fork[i]) //一旦在内存之内，直接输出
            {
                printf("访问内存%d：",fork[i]);
                ShowRam(ram,PhyNum);
                judge=1;
                break;
            }
            if(ram[j]==-1)//不在内存之中并且没有满 ，也直接输出
            {
                ram[j]=fork[i];
                lackingNum++;
                printf("访问内存%d：",fork[i]);
                ShowRam(ram,PhyNum);
                judge=1;
                break;
            }
        }
        if(judge==-1){
            ram[point]=fork[i];                    //在内存之内并且已经满了，FIFO置换
            point=(point+1)%PhyNum;
            replaceNum++;
            lackingNum++;
            printf("访问内存%d：",fork[i]);
            ShowRam(ram,PhyNum);
        }
        judge=-1;
    }
    ShowFinal( replaceNum, lackingNum, VisitNum);
}

void LRU(int fork[], int PageNum, int PhyNum, int VisitNum)
{
    printf("********************************************************************************\n");
    printf("*                                                                              *\n");
    printf("*                                  LRU算法                                     *\n");
    printf("*                                                                              *\n");
    printf("********************************************************************************\n");
    int ram[PhyNum];Init(ram,PhyNum);
    int time[PhyNum];Init(time,PhyNum);//time记录的是已经有的块号多久没使用了
    int judge=-1;
    int replaceNum = 0;//置换次数
    int lackingNum = 0;//缺页次数 

    for(int i =0;i<VisitNum;i++)
    {
        for (int k=0;k<PhyNum;k++)
        {
            if(time[k]!=-1){time[k]++;}
        }
        for(int j=0;j<PhyNum;j++)
        {
            if(ram[j]==fork[i]) //一旦在内存之内，直接输出
            {
                printf("访问内存%d：",fork[i]);
                ShowRam(ram,PhyNum);
                printf("time:");time[j]=0;for(int op=0;op<PhyNum;op++){printf("%2d",time[op]);}printf("\n");
                judge=1;
                break;
            }
            if(ram[j]==-1)//不在内存之中并且没有满 ，也直接输出
            {
                ram[j]=fork[i];
                lackingNum++;
                printf("访问内存%d：",fork[i]);
                ShowRam(ram,PhyNum);
                time[j]=0;
                judge=1;
                printf("time:");for(int op=0;op<PhyNum;op++){printf("%2d",time[op]);}printf("\n");
                break;
            }
        }
        if(judge==-1){                     //在内存之内并且已经满了，LRU置换
            int max=0;
            for (int k=0;k<PhyNum;k++)
            {
                if(time[k]>time[max])
                    max=k;
            }
            ram[max]=fork[i];
            time[max] = 0;
            replaceNum++;
            lackingNum++;
            printf("访问内存%d：",fork[i]);
            ShowRam(ram,PhyNum);
            printf("time:");for(int op=0;op<PhyNum;op++){printf("%2d",time[op]);}printf("\n");
        }
        judge=-1;
    }
    ShowFinal( replaceNum, lackingNum, VisitNum);
}

void OPT(int fork[], int PageNum, int PhyNum, int VisitNum)
{
    printf("********************************************************************************\n");
    printf("*                                                                              *\n");
    printf("*                                  OPT算法                                     *\n");
    printf("*                                                                              *\n");
    printf("********************************************************************************\n");
    int ram[PhyNum];Init(ram,PhyNum);
    int future[PhyNum];Init(future,PhyNum);//future记录的是未来多久要使用到
    int judge=-1;
    int replaceNum = 0;//置换次数
    int lackingNum = 0;//缺页次数 

    for(int i =0;i<VisitNum;i++)
    {

        for(int j=0;j<PhyNum;j++)
        {
            if(ram[j]==fork[i]) //一旦在内存之内，直接输出
            {
                printf("访问内存%d：",fork[i]);
                ShowRam(ram,PhyNum);
                future[j]=searchfuture(fork,i, VisitNum,ram[j]);
                judge=1;
                break;
            }
            if(ram[j]==-1)//不在内存之中并且没有满 ，也直接输出
            {
                ram[j]=fork[i];
                lackingNum++;
                printf("访问内存%d：",fork[i]);
                ShowRam(ram,PhyNum);
                judge=1;
                future[j]=searchfuture(fork,i, VisitNum,ram[j]);
                break;
            }
        }
        if(judge==-1){                     //在内存之内并且已经满了，LRU置换
            int max=0;
            for (int k=0;k<PhyNum;k++)
            {
                if(future[k]>future[max])
                    max=k;
            }
            ram[max]=fork[i];
            future[max] = searchfuture(fork,i, VisitNum,ram[max]);
            replaceNum++;
            lackingNum++;
            printf("访问内存%d：",fork[i]);
            ShowRam(ram,PhyNum);
        }
        judge=-1;
    }
    ShowFinal( replaceNum, lackingNum, VisitNum);


}

void CLOCK(int fork[], int PageNum, int PhyNum, int VisitNum)
{
    printf("********************************************************************************\n");
    printf("*                                                                              *\n");
    printf("*                                 CLOCK算法                                    *\n");
    printf("*                                                                              *\n");
    printf("********************************************************************************\n");
    int ram[PhyNum];Init(ram,PhyNum);
    int clock[PhyNum];
    int replaceNum = 0;//置换次数
    int lackingNum = 0;//缺//time记录的是访问号  
    int point=0;//指向循环队列中当前的位置
    int num=0;//统计循环查找的次数
    int NUM=0;//初始内存块有没有满
    for(int pp =0;pp<PhyNum;pp++){clock[pp]=0;}
    int judge=-1;
    for(int i =0;i<VisitNum;i++)
    {
        if(NUM!=PhyNum)
        {
            for(int j=0;j<PhyNum;j++)
            {
                if(ram[j]==fork[i]) //初始内存没满的时候，一旦在内存之内，直接输出
                {
                    printf("访问内存%d：",fork[i]);
                    ShowRam(ram,PhyNum);
                    clock[j]=1;
                    printf("1clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n");
                    judge=1;
                    break;
                }
                if(ram[j]==-1)//初始内存没满的时候，不在内存之中并且没有满 ，也直接输出
                { NUM++;
                    ram[j]=fork[i];
                    lackingNum++;
                    printf("访问内存%d：",fork[i]);
                    ShowRam(ram,PhyNum);
                    clock[j]=1;
                    printf("2clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n");
                    judge=1;
                    break;
                }
            }
        }
        else
        {   num=0;
            while(num!=PhyNum)
            {
                if(ram[point]==fork[i]) //初始内存已经满了，一旦在内存之内，直接输出
                {
                    printf("访问内存%d：",fork[i]);
                    ShowRam(ram,PhyNum);
                    clock[point]=1;
                    printf("3clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n");
                    judge=1;
                    point=(point+1)%PhyNum;
                    break;
                }
                num++;
                point=(point+1)%PhyNum;
            }
            int num=0;
            if(judge==-1)
            {     //-1说明不在内存中，1代表在内存中
                while(num!=PhyNum)//第一遍循环找访问为0；
                {
                    if(clock[point]==0)
                    {
                        ram[point]=fork[i];
                        clock[point]=1;
                        replaceNum++;
                        lackingNum++;//页次数
                        printf("访问内存%d：",fork[i]);
                        ShowRam(ram,PhyNum);
                        printf("4clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n");
                        point=(point+1)%PhyNum;
                        break;
                    }
                    point=(point+1)%PhyNum;
                    num++;
                }

                if(num==PhyNum)
                {
                    for(int pp =0;pp<PhyNum;pp++){clock[pp]=0;}//第二遍循环先将访问为都置为0，再一个个找过去
                    ram[point]=fork[i];
                    clock[point]=1;
                    point=(point+1)%PhyNum;
                    printf("访问内存%d：",fork[i]);
                    ShowRam(ram,PhyNum);
                    printf("5clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n");
                    replaceNum++;
                    lackingNum++;
                }
            }
        }

        judge=-1;
    }
    ShowFinal( replaceNum, lackingNum, VisitNum);
}

int main()
{
    printf("********************************************************************************\n");
    printf("*                                                                              *\n");
    printf("*                                                                              *\n");
    printf("*                   老师好，这是我的大作业，页面置换算法                       *\n");
    printf("*                                                                              *\n");
    printf("*                                                                              *\n");
    printf("********************************************************************************\n\n");

    int PageNum;                 //页面数量
    int PhyNum;                 //物理块数量
    int VisitNum;              //访问序列的长度
    int Visit[MAX_VISIRNUM];
    printf("请输入页面数量\n");
    scanf("%d",&PageNum);
    printf("请输入内存物理块数\n");
    scanf("%d",&PhyNum);
    printf("请输入访问序列长度\n");
    scanf("%d",&VisitNum);
    //12560365365604270435
    string inputSequence = "12560365365604270435";

    for(int i = 0; i < VisitNum; i++) {
        Visit[i]=inputSequence[i]-'0';
    }
//    cout<<inputSequence.length()<<endl;
    ShowVisit(Visit,VisitNum);

    while (1) {
        int fork[VisitNum];          //fork数组就是复制了Visit数组，相当于初始化随机序列
        for(int i =0;i<VisitNum;i++)
        {
            fork[i]=Visit[i];
        }
        printf("请选择你想使用的置换算法:\n");
        printf("1.FIFO 2.LRU 3.OPT 4.CLOCK 5.Belady&&FIFO 6.SIGN OUT\n");
        int want;
        scanf("%d",&want);
        switch (want) {
            case 1:
                ShowVisit(Visit,VisitNum);
                FIFO(fork, PageNum, PhyNum, VisitNum);printf("\n");
                break;
            case 2:
                ShowVisit(Visit,VisitNum);
                LRU(fork, PageNum, PhyNum, VisitNum); printf("\n");
                break;
            case 3:
                ShowVisit(Visit,VisitNum);
                OPT(fork, PageNum, PhyNum, VisitNum);printf("\n");
                break;
            case 4:
                ShowVisit(Visit,VisitNum);
                CLOCK(fork, PageNum, PhyNum, VisitNum);printf("\n");
                break;
            case 5:
                ShowVisit(Visit,VisitNum);
                printf("Belady\n");
                FIFO(fork, PageNum, PhyNum+1, VisitNum);printf("\n");
                break;
            case 6:
                printf("退出");
                break;
            default:
                printf("小老弟，你真皮!越界,请重新输入\n");
                break;
        }
    }
    return 0;
} 